package com.lun.swordtowardoffer2.c12;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeRange {

	public int[][] mergeIntervals(int[][] intervals){
		Arrays.sort(intervals, (i1, i2) -> i1[0] - i2[0]);
		
		List<int[]> merged = new ArrayList<>();
		
		for(int i = 0; i < intervals.length; ) {
			int[] temp = new int[] {intervals[i][0], intervals[i][1]};
			int j = i + 1;
			
			while(j < intervals.length && temp[1] >= intervals[j][0]) {
				temp[1] = Math.max(intervals[j][1], temp[1]);
				j++;
			}
			
			merged.add(temp);
			i = j;
		}
		
		int[][] result = new int[merged.size()][];
		return merged.toArray(result);
	}
	
}
